package sort;

import java.util.Random;

/**
 *
 * 快速排序
 *
 */
public class QuickSort {


    public static void main(String args[]){

        System.out.println("输入：");
        int nums[]=new int[]{2,7,1,3,6,9,1,5,8,4,9,2,23,4,3,6,7,8,8,1};
        printIntArray(nums);
        quickPart(nums,0,nums.length-1);
        System.out.println("\n输出：\n");
        printIntArray(nums);

    }

    /**
     * 递归
     * @param nums
     * @param begin
     * @param end
     */
    public  static void quickPart(int nums[],int begin,int end){

        if(begin>=end){
            return ;
        }
        int mid=partition(nums,begin,end);
        quickPart(nums,begin,mid-1);
        quickPart(nums,mid+1,end);
    }


    /**
     * 取最后一位为主元划分
     * @param nums
     * @param begin
     * @param end
     * @return
     */
    public  static int partition(int nums[],int begin ,int end){

        int a=nums[end];
        int i=begin-1;
        for(int j=begin;j<end;j++){
            if(nums[j]<=a){
                swap(nums,i+1,j);
                i++;
            }
        }
        swap(nums,i+1,end);
        return i+1;
    }

    /**
     * 交换
     * @param nums
     * @param a
     * @param b
     */
    public static void swap(int nums[],int a,int b){
        int temp=nums[a];
        nums[a]=nums[b];
        nums[b]=temp;
        return ;
    }

    //打印
    public static void printIntArray(int a[]){
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+"--");
        }
    }

}
